#! /usr/bin/env python
# -*- coding: utf-8 -*-

# Copyright (c) Huoty, All rights reserved
# Author: Huoty <sudohuoty@163.com>
# CreateTime: 2020-01-16 10:38:21


class Node(object):
    """单链表节点"""

    def __init__(self, data, next=None):
        self.data = data  # 数据域
        self.next = next  # 链接域，指向下一个节点


class SingleLink(object):
    """单链表"""

    def __init__(self):
        self.head = None  # 头指针
        self.tail = None  # 尾指针

        self._len = 0  # 记录链表长度

    def __len__(self):
        return self._len

    def is_empty(self):
        return self.head is None

    def add(self, data):
        """往尾部添加数据"""
        node = Node(data)
        if self.is_empty():
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self._len += 1

    def remove(self):
        """从头部删除数据"""
        if self.is_empty():
            raise KeyError("Link is empty")
        data = self.head.data
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self._len -= 1
        return data

    def __contains__(self, data):
        probe = self.head
        while probe is not None:
            if probe.data == data:
                return True
            probe = probe.next
        raise False

    def __iter__(self):
        probe = self.head
        while probe is not None:
            yield probe.data
            probe = probe.next

    def __add__(self, other):
        new = self.__class__()
        if self.is_empty():
            new.head = other.head
            new.tail = other.tail
        elif other.is_empty():
            new.head = self.head
            new.tail = self.tail
        else:
            new.head = self.head
            new.tail.next = other.head
            new.tail = other.tail
        new._len = self._len + other._len
        return new

    def __eq__(self, other):
        if len(self) != len(other):
            return False
        for s, o in zip(self, other):
            if s.data != o.data:
                return False
        return True

    def clear(self):
        self.head = self.tail = None
        self._len = 0


class LinkedQueue(object):

    def __init__(self):
        self._items = SingleLink()

    def __repr__(self):
        return "{}(size={})".format(self.__class__.__name__, len(self))

    def __len__(self):
        return len(self._items)

    def __iter__(self):
        return (item for item in self._items)

    def __contains__(self, item):
        return item in self._items

    def __add__(self, other):
        new = self.__class__()
        new._items = self._items + other._items
        return new

    def __eq__(self, other):
        return self._items == other._items

    def is_empty(self):
        return self._items.is_empty()

    def peek(self):
        return self._items.head.data

    def add(self, item):
        self._items.add(item)

    def pop(self):
        return self._items.remove()

    def clear(self):
        self._items.clear()


if __name__ == "__main__":
    q = LinkedQueue()
    q.add('a')
    q.add('b')
    q.add('c')

    for item in q:
        print(item, end=" ")
    print()

    print("is empty:", q.is_empty())
    print("length:", len(q))
    print("peek action:", q.peek())
    print("pop action:", q.pop())
    print("pop action:", q.pop())
    print("pop action:", q.pop())
    print("is empty:", q.is_empty())

    q.add('d')
    for item in q:
        print(item, end=" ")
    print()
